package ahaArithmetic;

//最少转机  图的广度优先遍历
public class Bfs_4 {

    static int map[][] = new int[][]{
            {1,2},
            {1,3},
            {2,3},
            {2,4},
            {3,4},
            {3,5},
            {4,5}
    };
    static int n = 5; //表示有五个城市
    static int map2[][] = new int[n][n];
    static int[] book = new int[n];
    static int head=0 , tail=0;
    static int start = 0;
    static Node_4[] nodes = new Node_4[n];

    public static void main(String[] args) {
        //给二维矩阵赋值
        for(int[] x:map){
            map2[x[0]-1][x[1]-1] = 1;
            map2[x[1]-1][x[0]-1] = 1;
        }
        //nodes初始化
        for(int i=0;i<n;i++){
            nodes[i] = new Node_4();
        }
        nodes[tail].dis = 0;
        nodes[tail].n = 0;
        tail++;
        book[0] = 1;
        bfs_4();
    }

    public static void bfs_4(){
        while(head<tail){
            //广度优先遍历
            for(int i=0;i<n;i++){
                //有路 且没有走过
                if(map2[start][i] == 1 && book[i]==0){
                    book[i] = 1;
                    nodes[tail].dis = nodes[head].dis+1;
                    nodes[tail].n = i;
                    nodes[tail].f = nodes[head].n;
                    tail++;
                    //判断成功
                    if(i==n-1){
                        print(tail-1);
                        return;
                    }
                }
            }
            head++;
            start = nodes[head].n;
        }
    }

    public static void print(int k){
        if(k==0){
            System.out.println(nodes[k].n);
            return;
        }
        print(nodes[k].f);
        System.out.println(nodes[k].n);
    }
}

class Node_4{
    int dis; //路程
    int n;  //几号城市
    int f;
}
